package first.forHuaWei.codeTop;

/**
 * @ClassName LC10II
 * @description:
 * @author: 荣燊
 * @create: 2021-09-13 10:50
 **/
public class LC10II {
    // 剑指 Offer 10- II. 青蛙跳台阶问题

    // 经典动态规划题
    // dp[i]表示青蛙跳上i级台阶的跳法，dp[i]=dp[i-1]+dp[i-2]
//    public static int numWays(int n) {
//        if (n == 1 || n == 0) {
//            return 1;
//        }
//        return (numWays(n-1)+numWays(n-2))%1000000007;
//        // 以上的写法超过时间限制，所有要考虑下记忆递归问题。因为f[n]与f[n-1]都要计算f[n-2]问题
//    }

    // 记忆递归法需要计算使用一个数组来保存数据。空间复杂度O(n)

    // 动态规划法
    public static int numWays(int n) {
        // 需要一个数计算
        int a = 1;
        int b = 1;
        for (int i=0; i<n; i++) {
            int sum = (a + b)%1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}
